#! /usr/bin/env python
# -*- coding: utf-8 -*-


class Solution:
    """
    @param nums: A list of integers
    @return: A integer indicate the subarray_sum of max subarray
    """
    def maxSubArray(self, nums):
        local_max = global_max = nums[0]

        for i in range(1, len(nums)):
            v = nums[i]
            local_max = max(local_max + v, v)
            global_max = max(local_max, global_max)

        return global_max

    # =================== 第二种方法: 自己想的 =====================
    def _maxSubArray(self, nums):
        l = len(nums)
        subarray_sum = [0] * (l + 1)

        # 求1到i的和
        for i in range(1, l+1):
            subarray_sum[i] = subarray_sum[i-1] + nums[i-1]

        max_sum = subarray_sum[1]        # 最大子数组和
        min_sum = 0        # 最小子数组和

        # print(subarray_sum)
        for i in range(1, l+1):
            # 获取0到i的最大连续和: 等于 "0-i的所有和" 减去 "0-i中最小的和" (注意都是以0开始的)
            # 相当于一条线段, 减去从开头起最短线段, 剩下的为最大线段!
            # local_max 是以i结尾的最大和
            local_max = subarray_sum[i] - min_sum
            # print(min_sum, subarray_sum[i])
            if local_max > max_sum:
                max_sum = local_max
            if subarray_sum[i] < min_sum:
                min_sum = subarray_sum[i]           # 0-i中最小的和

        return max_sum


def main():
    print("start main")

    nums = [-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-1000]

    # nums = [1,2,3,4,5,6,7,100,200,1000]
    s = Solution()
    print(s.maxSubArray(nums))


if __name__ == "__main__":
    main()
